public class code2 {
//    牛客 top101 有重复数字的全排列

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        // 按照字典序进行排序
        Arrays.sort(num);
        // 创建一个 boolean 类型的数组，设定数组的长度和 num 的长度相同
        // 用来标记每一个数组元素的使用情况
        boolean[] flag = new boolean[num.length];
        // 先将每一个元素都设定为 false 未使用状态
        for(int i = 0; i < flag.length; i++) {
            flag[i] = false;
        }

        // 创建一个和返回类型相同的数组，用于存放返回值信息
        ArrayList<ArrayList<Integer>> re = new ArrayList<ArrayList<Integer>>();

        // 再创建一个顺序表用来记录每一种状态下的元素
        ArrayList<Integer> arr = new ArrayList<>();

        // 实现一个方法获取每一个状态下的数字
        input(re, arr, flag, num);

        return re;
    }

    // 这里需要传入的参数为，re 记录所有可能状态的顺序表、arr记录当前出现的状态表、flag 记录每一个元素使用情况的顺序表、num 数组本身
    private void input(ArrayList<ArrayList<Integer>> re, ArrayList<Integer> arr, boolean[] flag, int[] num) {
        // 先设置一个返回条件
        // 这里的返回条件是，当这里的记录状态顺序表长度 == num 数组长度顺序表
        // 此时就意味着这是一种 子 状态
        // 记录到 re 中 并进行返回
        if(arr.size() == num.length) {
            // 这里需要注意的是要单独的创建出一个新的 ArrayList 表
            // 因为这是在同一个 arr 表中进行修改的，要记录一次的状态就需要单独进行一次表的创建
            re.add(new ArrayList<Integer>(arr));
            return;
        }

        // 之后来处理核心代码
        // 在这里还是需要将整个数组都进行遍历，每一个数字都需要进行记录
        for(int j = 0; j < num.length; j++) {
            // 首先，针对当前的单个元素是否被使用进行判断
            if(flag[j]) {
                // 当这个元素被使用过，此时就跳过这一次的循环操作
                continue;
            }
            // 还要针对一种情况进行判断
            // 因为这里会存在多个元素重复出现的情况
            // 此时，当元素 i 和 元素 i-1 相同时并且 i - 1 元素是已经被使用过的情况时。
            // 这就和 i 元素被使用过是一个道理，同样的需要跳过
            if(j > 0 && (num[j-1] == num[j]) && !flag[j - 1]) {
                // 需要注意的是，这里要防止数组越界的情况
                continue;
            }

            // 之后处理后续的元素添加操作
            // 先来将当前的元素设定为被使用状态
            flag[j] = true;
            // 将当前元素添加到 arr 顺序表中
            arr.add(num[j]);
            // 进行递归操作实现后续元素的提那几
            input(re, arr, flag, num);

            // 需要进行回溯操作，防止出现遗漏
            flag[j] = false;
            // 在回溯完成后
            // 此时需要将 arr 中的元素进行清空操作，只剩下第一个元素再次向后进行拼接
            arr.remove(arr.size() - 1);
        }
    }
}
